Labeled PSI from Fully Homomorphic Encryption with Malicious Security

发表于 更新于 分类于

恶意安全的全同态加密中的标签化 PSI

隐私保护集合求交（Private Set Intersection - PSI）允许双方，即发送方和接收方，在不向对方透露额外信息的情况下计算其私有集的交集。我们对不平衡的 PSI 设置感兴趣，其中（1）接收方的集合明显小于发送方的集合，以及（2）接收方（拥有较小的集合）有一个低功率设备。另外，在标签式 PSI 设置中，发送方为其集合中的每个项目持有一个标签，而接收方则从相交的项目中获得标签。我们在 Chen、Laine 和 Rindal（CCS 2017）的非平衡 PSI 协议的基础上进行了一些改进：我们增加了对任意长度项目的有效支持，我们构建并实现了一个具有小通信复杂性的非平衡标签化的 PSI 协议，并且在预处理阶段使用不经意伪随机函数（OPRF）加强了安全模型。我们的协议优于以前的协议：对于一个任意长度的 220 和 512 大小的集合的交集，我们的协议的总在线运行时间仅为 1 秒（单线程），总通信成本为 4MB。对于一个更大的例子，一个 228 和 1024 大小的任意长度项目集的交集，在线运行时间为 12 秒（多线程），总通信量小于 18MB。

1 介绍

1.1 隐私保护集合求交

隐私保护集合求交（PSI）是一个安全的计算协议，它允许两方，即发送方和接收方，以预先确定的大小计算他们的私有集和的交集，这样，接收方只能从互动中了解到 ，而发送方则一无所获。

PSI 有很长的历史，正面的用例包括从两个公司找到共同的客户，到隐私联系人的发现 [37]，以及验证密码泄露 [1]。

不平衡的 PSI (Unbalanced PSI)：大多数关于 PSI 的工作都是为平衡的情况设计的，在这种情况下，两个集合的大小大致相等，而且双方都有类似的计算和存储能力。当其中一个集合比另一个小得多时，这些协议通常只表现得稍微好一点。特别是，它们的通信成本至少与较大集合的大小成线性关系。然而，在某些应用中，接收者的集合可能比发送者的小得多。接收方可能是一个电池、计算能力和存储空间有限的移动设备，而发送方可能是一个高端计算设备。 此外，接收方和发送方之间的带宽可能是有限的。这促使人们研究不平衡的 PSI，其中一个集合比另一个大得多。最近有几个建议对不平衡 PSI 进行了优化 [12, 44, 47]。在这些工作中 [12] 实现了最小的整体通信复杂度，即 ，其中表示发送方的集合，表示接收方的集合，并且 。然而，他们的结果仅限于 32 位的项目，因为扩展到更长的项目会产生巨大的性能开销。在这项工作中，我们在功能、性能和安全模型方面改进了他们的协议。

标签化的 PSI (Labeled PSI)：在某些应用中，发送方为其集合中的每个项目 持有一个标签 ，我们希望允许接收方学习与交集中的项目对应的标签。换句话说，作为协议执行的结果，接收方应该学习 。当接收方的集合由单一元素组成时，这就等同于 [18] 首先考虑的（单服务器变体）关键词隐私信息检索（PIR）问题。为了便于阐述，我们将在本文的其余部分坚持使用标签化的 PSI 的概念，并注意到它等同于一个分批的单服务器对称的按关键词的隐私信息检索。

标签化 PSI 在隐私网络服务查询方面有一些直接的实际应用。例如，查询股票价格、具体位置信息、旅游预订信息或网络域名信息可以向服务提供商透露信息，允许他们进行高度有针对性的价格歧视 [40]，或获得敏感的个人或商业信息。另一个例子是私人联系人发现问题的变种 [37]，其中一个用户希望检索她的联系人列表中每个人的公钥，这些人已经注册了一个点对点通信的即时通信服务。在这方面，标签化的 PSI 可以提供必要的功能，同时保证查询隐私。

1.2 全同态加密

全同态加密（FHE）是一种加密形式，它允许任意（布尔或算术）电路直接在加密数据上进行评估，而不需要获得解密密钥 [7-10, 13, 17, 22, 24, 26, 49]。这种加密评估的结果仍然是加密的，并且可以由持有解密密钥的一方恢复。虽然 FHE 还远未成为在加密数据上进行计算的通用解决方案，但在特定场景下可以实现良好的性能，例如评估 AES 电路 [25]，计算 DNA 序列的编辑距离 [16]，以及训练逻辑回归模型 [34]。

在提高性能的道路上，一个基本的认识是，在许多情况下，所谓的 Leveled FHE 就足够了，其中加密方案的参数被选择为只允许预先确定的乘法深度的电路被评估。因此，出于性能方面的考虑，我们在这项工作中只使用 Leveled FHE，为了简单起见，我们有时会去掉 "Leveled" 前缀。

有几个 FHE 实现是公开可用的。我们选择使用同态加密库 SEAL1，它实现了 Brakerski/Fan-Vercauteren（BFV）方案 [22] 的变体 [4]。

FHE 参数和成本模型：BFV 方案的核心参数是三个整数：、 和 。我们根据 [11] 中提供的建议，将这些参数设置为始终达到至少位的安全级别。为了比较不同的参数选择，我们需要为 SEAL 的基本操作提供一些粗略的成本估算。每个密文的大小为 比特，而基础明文的大小为 比特。在计算方面，两个密文之间的乘法需要 位操作，而密文 - 明文的乘法需要 位操作（例如，见 [4]）。

1.3 我们的贡献

在高层次上，我们的贡献可以总结为以下几点：

  • 我们使用 OPRF 预处理阶段来实现比 [12] 更好的性能和安全性。特别是，我们实现了对恶意接收者的完全基于模拟的安全性，改进了 [12] 在半诚实模型中实现的安全性。
  • 我们在 [12] 的基础上，通过实现 [27] 的广义 SIMD 编码算法的修改版本，支持任意长度的项目。
  • 我们扩展了我们的协议，以小的通信复杂度实现了标签化的 PSI。然后，我们应用标签化 PSI 来提供更好的安全性，以防止恶意发送方。

首先，我们通过利用预处理阶段来改进 [12] 的协议，其中各方对他们的输入项目应用一个盲目的 PRF（OPRF）。这一变化有两个影响：

  1. 发送方不再需要像 [12] 中那样对结果密码文进行昂贵的噪声淹没操作。这允许实施者利用更有效的 FHE 参数，这进一步提高了我们的性能并增加了参数化的灵活性。
  2. 预处理阶段使我们能够论证我们的协议对恶意接收者是安全的。特别是，我们表明，在预处理阶段之后，模拟器可以提取接收器的集合，并成功模拟协议的其余部分。我们表明，这种预处理可以使用指数化 [31, 47] 或不经意传输 [36, 42] 进行。最重要的是，前者允许发送方只进行一次预处理，并在多次协议执行中重复使用，这在摊销的情况下大大改善了性能，例如在私人联系人发现中。

其次，[12] 中的所有例子都仅限于对 位的项目进行比较，而应用程序通常需要更长的项目，如电话号码、姓名或公共密钥。由于使用较大的 FHE 参数会产生很大的性能开销，因此对他们的协议进行明显的扩展以适应更大的项目具有次优的性能。我们通过实现 HElib 库 [27] 中使用的通用 SIMD 编码算法的 "懒惰" 版本来克服这一限制，该算法允许在不需要增加 FHE 参数的情况下将较少但较长的项目加密成单一的密文。

我们的第三个贡献是设计和实现了一个标签化 PSI 的协议。这种情况下的挑战是如何让接收者为每个项目学习一个标签，同时仍然保持通信的亚线性。尽管许多现有的 PSI 协议 [44, 47] 可以通过简单的修改来实现这一功能（在各自的 OPRF 值下加密标签），但它们都没有达到通信在大集合中是子线性的要求。我们提出了一种类似于原始 [12] 协议的方法，只是发送方评估了一个额外的多项式来插值标签。 当这些标签被适当地掩盖时，接收者将能够准确地恢复相交处的项目的标签。

第四，我们讨论了如何利用标签化的 PSI 的一个变体来实现对恶意发送者的合理安全概念。例如，[12] 的协议受到攻击，发送方可以强迫接收方输出其完整的集合 Y。在我们的协议中，接收方将输出，其中泄露由恶意发送方指定，并以合理的方式约束，表示集合的散列（见 7.3 节）。高层次的想法是执行标签化的 PSI，其中一个项目的标签是使用某个哈希函数得到的值。我们认为，发送方返回接收方项目的预期标签的唯一有效方式是让集合包含项目。我们所做的确切假设是，当是一个足够复杂的哈希函数时，发送方不能在给定的加密和一些预先确定的的幂的加密列表的情况下同态计算的加密。这个假设的有效性取决于使用平坦的 FHE 来评估深度高于预先确定的上限的电路的难度。对这一假设的任何有效攻击都可能代表着最先进的技术的重大进步。

第五，我们展示了 PSI 计算的输出是如何在双方之间秘密共享的。这立即允许使用任何通用的 MPC 协议对交叉点进行通用计算。这个扩展背后的想法是，发送方在所有返回的密码文中添加一个额外的随机值。 当接收者解密它们时，双方将持有一个比较结果的加法共享。从这样的共享中可以对交叉点进行额外的计算。例如，可以计算出交集的 Cardinality，或标签的总和。

1.4 相关的工作

1.4.1 不平衡的 PSI (Unbalanced PSI)

如前所述，我们的协议可以被看作是 [12] 基于 FHE 的协议的后代。 由于与我们的协议有很大的重叠，我们把对这项工作的回顾推迟到第 2 节，在那里有详细的描述。

另一项密切相关的工作是 Resende 等人 [47] 的工作，该工作优化了当发送方拥有比接收方大得多的集合时 PSI 的通信开销。他们协议的核心技术是对接收方的集合应用 ，以获得一个新的集合 。这里，发送方持有密钥，并能在本地对其集合应用 ，以获得 。为了减少通信，发送方在将 转发给接收方之前对其进行压缩。虽然这种压缩确实减少了通信量，但它仍然与较大集合的大小成线性关系，并可能引入假阳性。也就是说，在高压缩率下，接收方以不可忽略的概率输出 中的一个元素。

另一项遵循与 [47] 类似框架的工作是 Kiss 等人 [35] 的工作。这些协议的主要区别在于对 和压缩技术的选择。[47] 使用基于 Diffie-Hellman 的 ，而 [35] 使用乱码电路来遗忘评估 AES 函数。这种改变大大改善了发送方将 应用于其集合所需的计算工作，其代价是当 应用于接收方的集合时，通信和计算的增加。第二个区别是，[35] 使用了更保守的压缩技术和参数，没有引入明显的误判率。

1.4.2 有计算的 PSI (PSI with Computation)

能够在不透露中间结果，甚至不透露交集的情况下计算交集上的函数，往往是一个理想的属性。例如，[30] 建立了一个协议，它返回交集中所有项目的加权和。这个协议目前正被谷歌用于计算广告收入转换率。

Pinkas 等人 [44] 提出了一个 PSI 协议，旨在对交集进行任意的计算。虽然他们的协议效率很高，但它在可以自然进行的计算类型方面有一些限制。也就是说，如果正在计算的函数对输入的顺序敏感，就会引入大量的开销。尽管有这个限制，还是考虑了几个有趣的应用，比如门限 PSI，它根据交集大小是否达到某个门限返回真或假；[20，44] 考虑 PSI 的 Cardinality，它返回交集的大小。[39] 考虑了一个隐私的寻找朋友的场景。

Ciampi 和 Orlandi [19] 也设计了一个协议，可以计算交点上的任意函数。所有这些作品都有一个局限性，就是通信复杂度在两个集合的大小上至少是线性的，而我们的方法在发送方的集合大小上仍然是亚线性的。

1.5 按关键词的隐私信息检索 (PIR by Keywords)

隐私信息检索（PIR）允许用户检索由一个或多个服务器持有的某个数据库中的条目。Chor 等人在 [18] 中考虑了一种被称为按关键词的 PIR 的变体，其中用户查询由一个关键词而不是数据库中的条目地址组成。我们的标签化的 PSI 协议可以被看作是一个多查询（单服务器）的按关键词的 PIR：我们把接收者的集合看作是一个关键词集合，而把发送者的标签集合看作是数据库。

在 [23] 中，Freedman 等人介绍了一个基于加法同态加密的单服务器按关键词的 PIR 协议。我们在第 5 节的标签化的 PSI 协议使用了与他们相同的插值多项式。同时，使用 leveled FHE，我们每个关键词的通信量是 ，而 [23] 使用加法同态加密，他们的通信量是整个数据库大小的线性，即 。我们的标签化的 PSI 协议也可以处理多个关键词，所以它可以被看作是对其单一关键词搜索协议的改进。标签化的 PSI 也在 [31] 中被考虑，作者在那里构建了一个基于 Diffie-Hellman 类型假设的解决方案，通信量在较大的集合中呈线性。

Angel 等人 [2，3] 将多查询单服务器的按关键词的 PIR 作为一个匿名通信协议的核心部分。为了将按关键词的 PIR 减少到 PIR，他们向每个客户端推送了一个索引到关键词映射的布隆过滤器表示。他们还通过使用二幂选择和布谷鸟散列技术对多查询进行了优化。

Olumofin 和 Goldberg [41] 使用信息理论上的按关键词的 PIR 来保护客户对公共数据库查询的隐私。他们从按关键词的 PIR 还原到依赖于 B + 树和完美哈希函数的 PIR。

1.5.1 对数据库的隐私查询 (Private queries to databases)

Wang 等人 [51] 使用函数秘密共享而不是 PIR 来实现保护公共数据库查询隐私的相同目标。他们将查询建模为一个应用于数据库的函数。客户端向多个服务器发送该函数的秘密共享，然后结合响应以获得结果。只要至少有一个服务器不与其他服务器串通，就能确保查询隐私。

Boneh 等人 [6] 使用 FHE 来允许私人联合查询。该协议将匹配记录的索引返回给客户，客户随后可以发出 PIR 查询，以便自己获得记录。通信量与整个数据库的大小成正比。

Cheon 等人 [14, 15] 提出了允许用户在自己的密钥下对同态加密的数据库进行私人搜索和计算的技术。他们的方法支持不同种类的查询，如搜索和、搜索和最大、以及连接查询，利用二进制电路进行平等检查和比较。

Khedr 等人 [33] 从同态加密中构建了一个安全的电子邮件垃圾邮件过滤器和一个安全的多关键词搜索。通过在 GPU 平台上工作，利用并行性，他们取得了良好的性能。与其他关键词搜索协议相比，他们的协议有二进制输出：如果加密文件中存在一组关键词，则为真，否则为假。

1.6 符号

  • 是发送方的集合； 是接收方的集合。我们假设 。
  • 是 和 中集合元素的长度。
  • 是标签化的 PSI 中标签的长度。
  • 是我们 FHE 方案中的环维度（2 的幂）； 是密文模数； 是明文模数 [21，22]。
  • 是 SIMD 编码中扩展字段的度数。
  • 是布谷鸟哈希表的大小。
  • 是我们在 PSI 协议中用来分割发送方集合的分区数量 （遵循 [12]）。
  • 表示 的集合，而 是 的情况的缩写。

2 CLR17 协议

现在我们详细回顾一下 [12] 的协议。按照 [43] 的架构，他们的协议指示接收方为其集合 构建一个布谷鸟哈希表。具体来说，接收方将使用三个哈希函数 、 、 和一个矢量 的 个仓。对于每个 ，接收方将把 放在 的仓中，对于一些 ，使所有仓最多包含一个项目。发送方将执行一个不同的散列策略。对于所有 和所有 ，发送方将 放入 的仓中。请注意，当 时，发送方一侧的每个桶将包含 个高可信度的项目。 然后，可以认为 的交集等于所有桶际交集的联合。也就是说： 其中 是桶 中的唯一项目（或者在 为空的情况下，是一个特殊的哨位值）。然后该协议规定了一种使用 FHE 计算 的方法。接收者首先向发送者发送一个 的加密，表示为 ⟦⟧ ，发送者在本地计算： ⟦⟧⟦⟧ 当 时，观察到乘积中的一个项是零，因此 ⟦⟧ 将是零的加密。 ⟦⟧ 被返回给接收者，接收者得出结论：如果 ，则 。在 的情况下，乘积将是差异的乘积。发送者使用一个均匀采样的元素 对一些用于编码项目的有限基场 进行随机化。因此，当且仅当 时， 。否则， 是均匀分布的，并且与集合 无关。

在这个一般协议的基础上，[12] 提出了几个优化方案，使这个电路的计算变得高效。首先，回顾一下，接收器有一个由 个仓组成的向量，每个仓包含（最多）一个元素 。每个 必须与 相交。FHE 自然支持一种技术，允许加密向量并对加密的向量进行单指令多数据（SIMD）操作（[50]）。通过这种方式，许多项目 可以被加密成一个单一的密文，并同时进行处理，这将导致性能的显著提高。

尽管如此，直接计算 ⟦⟧⟦⟧ 被观察到效率很低，因为使用 FHE 对加密值评估大度多项式的性能惩罚。对于 ，直接计算 的乘法深度是 ，[12] 使用窗口技术将其减少到 。也就是说，观察 可以被看作是一个多项式 其中 由 和 决定。发送方需要计算 在 和 之间的所有幂的加密。鉴于只有 的加密，这可以在 深度内使用平方和乘法算法完成。例如，如果接收者发送 ， ， ，... ， 的加密，发送者可以使用这些条款以 的乘法深度计算所有必要的 y 的幂。他们还将发送方的分仓划分为 α 个子集。然后，发送方可以独立处理这些子集中的每一个。这将乘法深度进一步降低到 。这种方法的缺点是，对于每个 来说，必须将几个响应的密文 送回给接收方，使响应的大小增加了一个系数 。最后，作者使用模数转换技术来减少返回通信。

3 物品长度较长的 PSI

[12] 协议对 32 位的项目实现了良好的性能，并且在发送方一侧很好地扩展到非常大的集合。然而，由于以下原因，它对较长项目的扩展性较差。假设有效项目长度为 比特。那么他们需要将 FHE 方案中的明文模数设置为 。现在让 表示在发送方的同态评估的深度。在 [12] 中，深度 以双对数方式取决于 。因此，为了我们的目的，我们假设 是一个常数。那么，BFV 方案需要 来保证正确性，但利用第 1.2 节的复杂度估计，我们可以看到 [12] 的通信成本随着 线性增长；另一方面，计算成本随着 平方次增长，这是不理想的。

大 的另一个副作用来自于安全要求：它促使 FHE 参数 和 上升，为了保持安全水平，参数 也需要增加。现在可能出现两种情况：如果 与 相比很大，那么由于增加 会增加每个密码文的槽的数量，我们最终使用较少的密码文，性能开销很小；另一方面，如果 与以前的 值大小相似，那么在切换到新的 值后，许多槽可能仍未使用，这意味着通信成本增加而没有好处。

无论项目的初始长度如何，习惯上都是应用输出长度为的哈希函数，并在这些短哈希上执行相交协议。这里表示统计安全参数。在实践中，我们设定，因此我们要求 大约为 。然而，使用如此大的 值对 [12] 协议的性能有巨大影响。在这项工作中，我们通过使用 [50] 中提出的通用 SIMD 编码方法来解决这个问题，它允许对长度和宽度灵活的向量进行系数明智的操作。更确切地说，对于一个可调整的参数 ，我们可以对长度为 的向量进行操作，其中每个条目可以采取不同的 值（当 时，这就是 [12] 中使用的 SIMD 方法）。

更确切地说，BFV 方案的明文空间等于 。假设 是一个素数，而 被分解成一个不可还原的多项式 的乘积，每个多项式的阶都是 。此外，假设 是最小的正整数，使得 。那么 SIMD 编码可以解释为以下两种同构关系

其中是一个固定的有个元素的有限域。现在，SIMD 编码对应于◦，而解码是同构的 ◦。

3.1 用更宽的插槽进行 SIMD 的权衡

通信成本：我们的 PSI 协议的具体通信成本可以通过以下方式计算：查询由 密文组成，其中 是一个密文中支持的槽的数量，而。每个密文的大小为 比特。在这里 ，因为有限域 中的每个元素都可以代表一个大小为 比特的项。发送方的回复由 个密文组成，每个密文的大小约为 比特。

我们把 （和）、、 和 视为常数。那么，查询大小是 的恒定倍数，所以增加 会增加查询大小。然而，在我们的设置中，我们通常有 。由于 总是小于 ，所以 项占主导地位。对于较大的 来说，回复的大小也会稍差，但其影响很小。

计算成本：发送方的在线计算由复杂度为 的同态乘法组成，每次需要 比特的操作。在隐藏所有常数后，我们看到计算成本是 ，所以增加 对在线计算时间有直接的积极影响。

选择不同 的效果：使用较大的 值有另一个隐含的好处：它允许在相同的项目比特长度下选择较小的 ，因此可以选择较小的 ，这也为选择较小的 提供了可能。 计算成本是 比特的操作，通信成本是，所以计算和通信都只依赖于 值的对数。因此，当其他参数保持固定时，n 对性能的影响是微不足道的。

我们的结论是，在相同的设置下，使用更宽的槽（即更大的 值）来编码项目会导致更大的通信和更小的在线计算。

3.2 懒 SIMD 编码算法

[50] 提出，可以利用 FFT 算法进行快速的 SIMD 编码和解码。当 较小时，FFT 算法非常有效，但对于较大的 值，存在更有效的算法。例如，HElib 库 [27] 分两步进行编码。令 。他们首先通过 个场同构将 映射到 。然后用一个基于树的 CRT 算法来反转第一个映射 ：给定 ，返回 ，这样 。

我们注意到，第二个映射 在编码中有时可以省略。事实上，如果希望对 个槽中的项目进行同态置换，它是必要的。由于我们目前的应用不需要这种置换，我们可以跳过这一步，只使用 和它的逆向来进行解码和编码。这样可以节省计算时间和存储空间，因为评估 需要 的同构信息。

另一方面，FFT 算法可以在一个步骤中执行 ◦，而且有快速算法可以处理 的模数。然而，在这种情况下利用 FFT 的自然方式似乎需要处理长度为 的数据，使用 中的 次方的统一根。这种算法的复杂度是 中的 运算。

为了确定最佳策略，我们通过使用 FLINT [28] 实现懒惰编码算法和 FFT 算法进行了比较，并在表 1 中展示了结果。从结果中我们可以看出，懒惰编码算法有一个速度优势，这个优势随着扩展度 的增加而增加。

image-20220524160703773
表 1：SIMD 编码算法的比较

4 OPRF 预处理

我们现在演示如何进行预处理阶段以促进更有效的在线阶段。其核心思想是首先使用不经意伪随机函数 ( ) 处理用于求交的值，其中只有发送者知道 的密钥。这样做的效果是，可以消除 [12] 为保护发送者集合而采用的几种昂贵的反措施。

4.1 CLR17 的方法

[12] 协议执行噪声淹没以证明发送者的安全性。这样做的必要性源于这样一个事实：同态操作中的噪声增长不仅取决于被操作的密文，而且还取决于底层的明文。因此，如果结果密码文在最后没有被重新随机化，如果底层的噪声分布没有被适当数量的比特淹没的噪声所隐藏，那么他们的安全证明就不能发挥作用。

这种方法至少有两个不同的问题。首先，它要求发送者估计噪声大小的启发式上界，并确保有足够的噪声空间来执行适当数量的噪声泛滥。这使得他们的协议不可能在小的 FHE 参数下运行，即使是对于非常小的集合。另外，他们的协议对恶意攻击是脆弱的。例如，接收方可以在其密码文中插入更多的噪声，导致发送方的噪声淹没比它想象的要少。现在，通过检查 PSI 计算后的噪声分布，接收方有可能获得关于发送方集合的额外信息。

4.2 我们的解决方案

我们采取了一种不同的方法来解决这个问题，使我们能够完全摆脱噪音泛滥。也就是说，在进行 PSI 协议之前，我们使用 对双方的项目进行散列。这确保了发送方的项目 在接收方看来是伪随机的，防止接收方了解关于原始项目的任何信息，即使它完全了解了散列值。

简而言之，我们让发送方选择一个密钥，并在本地计算。然后，接收方以交互方式将 应用于其集合，得到。从安全的角度来看，现在将发送给接收者是安全的，接收者可以从推断出交集。然而，这种方法产生了非常高的通信开销，因为可以很容易地超过一千兆字节。最近的几项工作 [44, 47] 试图通过将以压缩格式编码来解决这个问题，例如布隆过滤器或布谷鸟过滤器。然而，通信仍然是线性集合，而且压缩可能会引入假阳性，如 [47] 的情况。

我们的方法避开了这个问题，将基于 FHE 的 PSI 协议来处理和这两个集合。总的来说，我们的协议的通信复杂度是，而不是，例如 [44, 47] 的情况。如前所述，我们不需要像 [12] 那样担心噪音泛滥，因为 已经提供了足够的保护。这使得我们的协议可以使用高度优化的 FHE 参数，提高我们的性能和通信开销。

更广泛地说，将 应用于集合，也就不需要执行另外两个保护发送方集合的程序。首先，回顾一下，发送方执行简单的散列，即使用三个散列函数将其项目映射到个桶。在最初的 [12] 协议中，所有这些仓必须用假项目填充到一个上限。这可以防止一些部分信息被泄露给接收者，例如，个项目被哈希到第个桶，这意味着。然而，在应用 的情况下，任何给定桶的内容物数量是的函数，因此可以被公开。

其次，发送方使用接收方的集合评估的多项式不需要是随机的。回顾一下，在 [12] 中，发送方以同态方式评估了一个形式为的多项式，其中在每次执行协议时都会被均匀地随机抽样。这个额外的随机化是必要的，以确保接收者不了解和之间的差异乘积。它对性能也有很大的影响，因为它增加了一个乘法深度。然而，在应用 之后，这个多项式是针对的，而不是形成的，因此，揭示差异的乘积不再是一个安全风险，因为可以安全地被公开。

我们考虑两种类型的 ，它们有不同的权衡。第一种是由 [31, 47] 描述的基于 Diffie-Hellman 的 ，它允许发送方与许多独立的接收方重复使用 值，允许对发送方的集合应用 的成本被摊销。另外，还可以使用基于 OT 的 [36, 42]，这在计算上更有效率，但不能在多个接收者之间重复使用。

4.3 DH-OPRF 预处理

基于 Diffie-Hellman 的 OPRF 协议计算函数 ，其中 是一个哈希函数，被建模为一个随机预言机。这种类型的 OPRF 已经在 PSI 的背景下被多次使用，例如在 [23, 31, 38, 47]。更详细地说，令为一个阶数为的循环群，其中 One-More-Gap-Diffie-Hellman（OMGDH）问题很难解决。是一个范围为的随机预言哈希函数。发送方有一个密钥，接收方有一个输入，。接收者首先选择一个随机数，并将发送给发送者，发送者返回一个。然后接收方可以输出。外层哈希函数用于将组元素映射到一个足够长的比特串，并有助于在恶意设置中促进提取。

特别是，通过观察对的查询，模拟器可以收集一个值为的组元列表，这些都是接收者已知的。从这个列表中，模拟器可以计算出这个集合。对于的某个子集，接收方将发送给模拟器，模拟器再返回。为了让接收方了解的 OPRF 值，它必须将发送到随机预言机。这时，如果，模拟器可以提取 。虽然这个 OPRF 不便于在发送第一个消息时提取所有的，但在接收者得知 OPRF 值之前就进行了提取，这对我们的目的来说是足够的。

在我们的 PSI 协议中，这种 OPRF 的特性是发送方可以对多个接收方使用相同的密钥。这使得拥有一个庞大且通常相对静态的集合的发送方只需预处理一次其集合。这一点特别有价值，因为我们的协议还允许从预处理的数据集中有效地插入和删除数据。

4.4 OT-OPRF 预处理

另一种方法是使用最近的不经意传输（OT）扩展协议的进展 [36, 42]，它能够实现与传统 OPRF 非常相似的功能。相关的区别是，接收方对每个密钥只能学习一个 OPRF 输出。这一限制规定了 OPRF 必须以不同的方式使用。特别是，我们遵循 PSZ 范式 [36, 43, 45, 46]，其中 OPRF 在布谷鸟散列之后被应用于项目。首先，双方进行布谷鸟散列，确保接收方在每个哈希表仓中最多有一个项目。然后双方运行一个基于 OT 的 OPRF 协议，其中发送方为每个桶分配一个唯一的密钥。接收方用 OPRF 的输出更新布谷鸟表中的值，而发送方也同样更新其简单哈希表中的值。请注意，发送方可以学习每个键的任意数量的 OPRF 输出，这使得它可以更新每个桶中的所有值。

这种方法的另一个限制是，发送方必须用假项目填充其简单哈希表，以确保接收方不会推断出任何部分信息。也就是说，由于 OPRF 是在散列后应用的，任何给定的 bin 中的项目数量都是 的函数，而不是散列集 。因此，至关重要的是，像 [12] 中所做的那样，缓冲区被填充到其可能的最大尺寸。

与基于 Diffie-Hellman 的 OPRF 一样，接收器的输入可以被提取出来。这些协议如何提取的确切细节是相当复杂的，我们推迟到 [42] 进行详细解释。

5 标签化 PSI

我们提出了两种相关的方法来实现标签化的 PSI。前者与 [12] 协议兼容，而后者被优化为利用 OPRF 预处理阶段。本节将以接收方有一个单子集 ，并且当且仅当发送方有一对 在其集合中，而 时，获得标签 。这些方法通过在接收方使用布谷鸟散列，自然地扩展到一般的设置。

5.1 与 CLR17 兼容

我们采用插值多项式的思想，也是在 [23] 中使用的，来建立我们的标记 PSI 协议。记得在 [12] 协议中，服务器对多项式 进行同态评估，其中 是某个有限域 中的随机非零元素，而多项式 的系数是 中的基本对称多项式。它的属性是：如果 ，那么 ；否则 是 中的一个随机元素。在标签化的 PSI 的情况下，发送者的输入是一个成对的列表：，为了简单起见，我们假设 和 是 的元素。我们的目标是构建一个多项式 ，使得对于任何 ：

请注意，存在一个度数小于 的多项式 ，使得 ，对于所有 的情况，那么，我们随机选择 ，并让

很容易验证 G 具有所需的属性：如果 ，那么 ；如果 ，那么由于 ， 和 是随机的，我们知道 是 中的一个随机元素。在高水平上，我们的协议让接收方使用 FHE 方案加密并发送其每个项目 ；发送方以同构方式评估多项式 和 ，并将结果发送回来。然后，接收方解密并获得 ，如果 ，它要么等于 ，要么在 中均匀随机。

请注意，在上面的讨论中，我们隐含地假设标签的大小与项目相同。如果标签比项目长，我们可以把每个标签分解成几块，让服务器重复计算几次。最后，接收者可以解密标签的各个部分并重新组合。安全性证明不受影响，因为在不匹配的情况下，所有解密的部分将是随机字符串。

通信复杂度：我们利用了 [12] 中的优化，并对其进行了修改，即发送方同态地评估几个多项式而不是一个。因此，我们的标签化的 PSI 的通信复杂度等于 ，而在线计算复杂度为 ，其中 和 分别表示项目和标签的长度。注意，通过事先对项目进行散列，我们可以假设 ，其中 是统计安全参数。

计算复杂度：这个标签化的 PSI 协议在 [12] 的 PSI 协议基础上引入了两个额外的计算任务。在离线阶段，发送方需要插值一个次数为 的多项式。牛顿插值算法的复杂度为 ，对于小的 值来说是很快的。该算法需要执行 次，所以总的复杂度是 。在在线阶段，发送方需要对内插的多项式进行同态评估，其成本为 的 FHE 操作。与 [12] 中的 PSI 协议的复杂性相比，发送方对有标签的 PSI 的计算增长了 ，即标签长度和项目长度的比率。

5.2 OPRF 优化标签化 PSI

如果各方进行 OPRF 预处理阶段，这个程序可以得到明显的改善。其核心思想是首先使用相关的 OPRF 值作为密钥对所有的标签进行加密。然后，所有这些加密的标签可以被发送给接收方，接收方使用其集合中的项目的 OPRF 值来解密相关的标签。我们强调，这种方法不需要同态加密方案的安全保证，以确保不在交集内的项目的标签信息不会泄露给接收者。

为了避免在发送这些加密标签时的线性通信，我们让发送者评估一个多项式，该多项式对加密标签进行插值，有效地压缩了需要通信的数据量。更详细地说，发送方首先对其集合 中的所有 计算（）（）。这里， 将被用作计算交集的 OPRF 值，如前所述，而第二部分 将被用于一次一密地加密标签，即 。然后发送方计算一个最小次数的多项式 ，使得 。

这种方法的主要优点之一是，由于 不需要额外的随机化，所以在线计算的程度有所降低。回顾上文，评估对称多项式 F 的结果必须通过与非零 相乘来随机化。这使计算的程度增加了一个，这可能需要更大的 FHE 参数。

展望未来，我们对恶意发送者的安全改进方法需要使用标签化 PSI，但有趣的是不需要将评估的对称多项式 送回给接收者。因此，通过在计算标签时不要求 ，我们在恶意设置中通过不计算或评估 F 获得了额外的性能改进。

5.3 完整协议

我们在图 2 中介绍了我们标记的 PSI 的完整协议。

image-20220524161313706
图 2：标签化 PSI 协议

  • 输入：接收方输入大小为 的集合 ，；发送方输入大小为 集合 ，， 和 分别表示计算和统计安全参数。

  • 输出：接收方输出 ；发送方什么也不输出。

  • 步骤：

    1. 发送方执行 OPRF：发送方为 OPRF 函数 采样一个密钥 。发送方将其集合更新为 。这里 是一个随机预言哈希函数，其范围为 位，使用掷硬币协议进行采样。

    2. 哈希：参数 是商定的，这样布谷鸟散列 个球到 个桶的成功率大于等于。三个随机哈希函数 是用掷硬币的方式商定的。发送者将所有 插入到集合 中。

    3. 选择 FHE 参数：双方确定 IND-CPA 安全 FHE 方案的参数 ，，， 。他们选择 ， 要足够大，以便 。

    4. 选择电路深度参数：双方确定分割参数 和窗口参数 ，以最小化整体成本。

    5. 发送方对集合 进行预处理：

      1. 分割：对于每个集合 ，发送者将其分割成尺寸最大为 的 个子集，并表示为。
      2. 计算系数：
        1. 对称多项式：对于每个集合 ，发送方计算 上的对称多项式 ，使 ，对于 。
        2. 标签多项式：如果发送者有与其集合相关的标签，那么对于每个集合 ，发送者在 上插值多项式 ，使得 ，对于 ，其中 是与 相关的标签。
      3. 批处理：将多项式 看作一个矩阵，其中 索引行。对于每一组 行（非重叠和连续的），将它们视为属于一个批次。对于第 批和每个 ，取 个多项式的第 个系数，并将它们批为一个 FHE 明文多项式 。对于标签化的 PSI，对标签多项式 进行同样的批处理，形成批量的 FHE 明文多项式 。

    6. 接收方加密集合 ：

      1. 接收方执行 OPRF：接收者使用其随机顺序的集合 作为隐私输入，执行 [31] 的交互式 OPRF 协议。发送方使用密钥 作为其隐私输入。接收方学习 ，并设置。
      2. 布谷鸟哈希：接收方使用 的哈希函数对集合 进行布谷鸟哈希运算，形成一个有 个桶的表 。
      3. 批处理：接收方将 解释为一个长度为 的矢量，元素在 中。对于 中的第 组 （非重叠和连续），接收方将它们分批放入一个 FHE 明文多项式 中。
      4. 窗口化：对于每个 ，接收方计算分量的第 次幂，其中，。
      5. 加密：接收方使用 对每个幂进行加密，并将密文给发送方。

    7. 发送方计算交集：对于第 批

      1. 同态计算所有幂的加密：发送方收到密文集合 ，并以同态方式计算出一个向量 ，其中 就是加密的同态密文。

      2. 同态计算点积：对于每个，发送方同态计算

        并可选择对密文 ， 进行模数转换以减少其大小。所有 都被送回给接收方。如果需要标签化的 PSI，对 重复同样的操作，并表示返回的密文 。

    8. 解密并获得结果：对于第 批，接收方对密文 进行解密，得到 ，它们被解释为 中 元素的向量。

      令 为 中 个元素的向量，通过串联。对于所有的 ，输出相应的 ，如果

      其中 是 在 中占据的仓的索引。

      如果需要标签化的 PSI，对 密文进行同样的解密和连接过程，得到 个元素向量 。对于上述每个，输出相应的 的标签为 。

6 带有计算的 PSI

最近 PSI 协议的一个趋势是在交叉点上实现额外的计算 [19, 20, 30, 44]。然而，在我们的设定中，集合的大小是极其不平衡的，这些协议带来了（至少）线性的通信开销。我们表明，我们的协议可以被扩展，以适合进一步计算的形式输出交集和相关的标签。通过这些技术，双方可以输入一组键值对 ，其中具有匹配键值的 是函数 的输入。

这种计算的通信复杂度是 ，其中 是在 输入上计算 f 的通信复杂度。这与其他技术（如 [19, 44]）不同，后者要求通信复杂度至少为 。在 的情况下，这代表了一个显著的节约。此外，在我们的协议中，接收器的工作与 成正比，当接收器是一个轻量级的设备，如手机，这可能具有实际意义。

其核心思想是返回结果的加法秘密份额，这可以作为输入转发给二级 MPC 协议。为了简单起见，首先让我们考虑没有标签的情况，并且我们的 PSI 协议是使用单一分割来执行的。在标准的 PSI 协议中，有一个分割意味着在解密后，接收方持有一个单一的结果向量 ，其中 是零，如果其布谷鸟表第 个位置的项目是在交集中。

发送方不返回 ，而是返回一个密文 ，其中 是一个均匀随机值的向量。当接收方解密密文时，它将持有 2-out-of-2 的秘密共享 ，它可以被转发到二级 MPC 协议并被检查为零。例如，交集的 cardinality 可以由电路计算： 𝟙 在实践中，我们发现，我们的协议通过利用一个以上的分割获得了更好的性能。这样做的效果是，对于接收方布谷鸟表中的每个位置 ，发送方返回 个结果 ，接收方从中得出结论，如果 ，它在布谷鸟位置 的项目是在交集中。因此，可以计算出 cardinality 为 𝟙 。我们注意到，虽然 PSI 协议的主要阶段可以从适度的大小 中受益，但其他参数，例如窗口大小，可以增加，以确保 是一个常数，如 或甚至 。

除了简单地计算相交点外，还可以返回标签的秘密共享。当相同的基于秘密共享的基本方法被应用于发送方持有的标签 时，接收方将解密共享 。我们注意到，对于接收方来说，为其集合中的每个项目提供相关数据是很直接的。这些数据可以简单地与布谷鸟表中的每个项目一起存储，并适当地作为输入提供给 MPC 协议。

在发送方收到函数 f 的输出的情况下，重要的是， 所进行的计算是对称的。这意味着输入的排序不会影响计算。这一要求是与 [44] 共享的，源于布谷鸟散列的使用。特别是， 的输入是由接收者的布谷鸟散列表排序的，这是其私人输入的一个函数。因此，如果函数不是对称的， 的输出可能会泄露私人信息。我们注意到，当接收方获得 的输出时，不需要这种对称性要求，因为它已经知道了排序。

7 恶意模型下的安全

我们现在表明，我们的协议对恶意的接收者是安全的，同时对恶意的发送者提供隐私 [29]。理想的功能呈现在图 3 中。观察一下，恶意方被允许拥有比他们诚实时更大的集合。确切的集合大小将在证明中讨论。

image-20220524163315438
图 3：理想的 PSI 功能

参数：诚实的发送方和接收方有各自的集合大小 , 。如果发送方或接收方是恶意的，那么他们的集合大小分别为或。

  • 在接收方的输入中，其中，如果接收方是诚实的，确保；若为恶意的，则。随后将交给发送方。
  • 此后，对来自发送方的输入，其中，如果发送方是诚实的，确保；若为恶意的，则。随后将输出交给接收方。

7.1 单边模拟

粗略地说，要证明图 2 的协议 具有单边模拟性 [29]，我们必须证明，对于所有恶意的 PPT 接收者 ，存在一个模拟器 ，使 在真实协议 中的交互与 在与图 3 的理想功能交互时的输出无法区分。更正式地说，请考虑定理 1。

定理 1：在随机预言机混合体和 OMGDH 困难群 存在的情况下，图 2 的协议 以单边模拟安全性 [29，定义 2.2] 安全地计算 PSI 功能（图 3），其中 。

证明：首先，观察一下，步骤 1 到 5 不涉及接收方，因此模拟起来很简单。在步骤 7a，接收方在 组中执行 OPRF 调用，其中模拟器 扮演发送方的角色。在步骤 7e，接收方对其查询进行同态加密，并将其发送给发送方。此时， 使用随机预言机从 OPRF 调用中提取接收方的输入 （见第 4.3 节）。 被转发到理想功能，它的响应是 。模拟器用不在 中的随机值填充 ，大小为 ，然后用 执行步骤 1 到 5，就像诚实的发送者用 做的那样。 完成协议（步骤 8），扮演诚实发送者的角色。

这个模拟器的正确性直接遵循了 [31] 的证明。特别是，除了被提取的 之外，所有的 OPRF 值在接收者的视野中是均匀分布的。因此，用不在 中的值填充 会引起同样的分布。与 [31] 相比，我们协议的主要区别是使用 FHE 来压缩通信量。

7.2 接收者隐私

在我们的环境中，实现针对恶意发送者的完全基于模拟的安全是极具挑战性的。可以说，最重要的障碍是，我们要求通信复杂度在发送者集合的大小上是亚线性的。这使得传统的提取其集合的方法，例如 ZK 证明 [31]，由于相关的通信开销是线性的，因此不可行。

第二大挑战是强制要求发送方执行正确的计算。在我们的协议中，发送方可以以多种方式偏离规定的协议。例如，众所周知 [23, 48]，发送方可以不正确地执行简单的散列，这使得接收方的输出分布取决于接收方的全集。此外，在我们的协议中，情况甚至更糟，因为发送方获得了接收器集合的同态加密副本。与其用它来评估我们的 PSI 电路，发送者有很大的自由度来计算一个不同的电路，它可能任意地依赖于接收者的集合。

例如，对于发送方来说，强迫接收方输出他们的全部集合是微不足道的。回顾一下，在 [12] 和我们的半诚实协议中，当返回的密文包含一个零时，接收方解释为这意味着他们相应的项目是在交集中。那么，对发送方的直接攻击就是简单地加密并返回一个零的矢量，如果它持有一个公钥的话，否则就返回一个全零的密文。然后，接收方将得出结论，其全集是交集。

面对这些重大的挑战，我们选择放弃在有恶意发送者的情况下基于模拟的安全。相反，我们表明：（1）我们的基本协议实现了对恶意发送者的隐私 [29]；（2）对我们协议的简单修改可以大大限制恶意发送者可以执行的攻击类别。

Hazay 和 Lindell [29] 曾在 PSI 的背景下考虑过这种针对恶意发送者的隐私和针对接收者的完全安全概念。非正式地，隐私性保证了发送者的成绩单不会透露任何关于该接收者的输入。这是对基于全仿真安全的放松，例如，我们没有实现输入的独立性，也没有保证输出的正确性。关于正式的描述，我们请读者参考 [29，定义 2.2]。

定理 2：在存在语义安全的全同态加密方案和 OMGDH 硬组 的情况下，图 2 的协议 可以计算出 PSI 功能（图 3），并对恶意发送者具有隐私性 [29，定义 2.2]。

证明：接收者向发送者发送两个信息。首先是形式为 的 OPRF 查询，其中 是均匀随机采样的。根据 OMGDH 在组 中是一个困难问题的假设，用一个均匀的随机元素替换 是不可区分的，因此这些消息与接收方的集合无关。接收方发送的第二组消息是 FHE 加密的幂，将用于评估对称多项式。根据 FHE 方案语义安全的假设，用统一的随机值替换幂是不可区分的，因此这些信息也是独立于接收方集合的。

7.3 带有泄露的两边模拟

我们现在提出了一种限制发送方可以执行的攻击类型的技术。其核心思想是受标签化 PSI 的启发，结合使用支持更小深度的 leveled FHE 评估高深度电路的事实是困难的，甚至是不可行的。首先，我们考虑发送方不重复使用多个接收方的预处理阶段的结果的情况。

对于接收者来说，要得出一个项目 在交集中的结论，我们要求发送者返回一个标签 的加密，其中 是一个足够复杂的哈希函数，我们将其建模为一个随机预言机，例如 。由于 是一个随机预言机，发送方有两个选择来计算 ：(1) 它必须知道一些 ，并在本地计算 ；(2) 它必须使用接收方的 加密集来同态地评估一个电路，在双方同意使用的固定加密参数下，使用给定的分级 FHE 方案计算 。

我们启发式地论证了评估这样的电路是非常困难的 -- 如果不是不可行的话 -- 使用分级 FHE，其中的参数被选择为支持更小的乘法深度。虽然不能保证高阶多项式不能被评估，但我们在实验中发现，对于我们的参数，即使进行一些额外的乘法，噪音水平也总是溢出的。此外，像 这样的哈希函数具有非常高的深度，由于在二进制和模块化算术之间的切换（在 中），使用算术 FHE 方案来评估似乎非常困难。此外， 的深度可以通过重复应用哈希函数而任意增加，而且重复的次数可以在选择加密参数后决定。为了封装这个假设，我们定义了 的概念。

定义 3：如果对于所有的 ，下面的游戏输出 的概率可以忽略不计，我们就说一个分级的完全同态加密方案 是 的。均匀地对一个 进行采样，如果 ，则输出 ，否则输出 。

在给定的（分级）FHE 方案是 有限的假设下，发送方必须知道明文值 ，才能以不可忽略的概率计算出 的加密。因此，发送方被限制在选择一个多项式大小的集合 ，可能大于 ，并在 PSI 协议中使用它。特别是，模拟器可以将 提取为所有 ，从而使发送方查询了 。我们注意到，发送方并不承诺其集合 ，并且可以在每次协议调用中使用其中的任意子集。

另一方面，发送者仍然能够使交集间接地取决于集合 。特别是，发送者可以选择一个电路 ，理想功能被定义为： 这个泄漏函数的模型是，发送方可以对接收方的加密哈希表进行一些恶意的计算。这使得发送方可以根据 中的项目有条件地从交集中移除项目。完整的安全证明见附录 A。虽然这样的攻击在某些情况下可能是严重的，但这种泄漏比 [12] 中的泄漏要少得多，因为在 [12] 中，发送者可以强迫交集为 。

现在我们把注意力转移到发送方与多个接收方重复使用预处理阶段的情况。在这里，散列参数必须是固定的和重复使用的。特别是，布谷鸟散列函数和用于散列到 位字符串的散列函数 H 由发送方挑选。这与图 2 中的步骤 1 和 2 不同，在这两个步骤中，各方共同抽取随机哈希函数。这就意味着，发送方可以根据接收方的集合 来选择有条件失败的哈希函数。例如，如果 ， 在所有三个哈希函数下都哈希到布谷鸟位置 ，布谷鸟哈希将失败。这类失败可以被发送者观察到，并泄露出接收者的集合是所有在这些参数下无法进行布谷鸟散列的集合中的一员 -- 这是一个单一的信息。

虽然这种攻击可能很严重，但我们认为许多应用可以容忍泄露一个比特。可以采用的一个对策是对公共参考字符串的哈希函数进行采样。这可以大大限制这种选择性失败攻击的有效性，因为哈希函数是固定的。

8 实验

我们实现了我们的协议（任意长度的不平衡 PSI 长的项目的不平衡 PSI 和标签 PSI），并与以前的方法进行了基准测试。方法进行比较。对于长项和短项的不平衡 PSI，我们的 的比较点分别是 [5, 47] 和 [12]。对于有标签的 PSI，我们通过关键词与多查询的 Multi-PIR 进行比较。SealPIR 的解决方案 [2]。

我们的实现是在同态加密库 SEAL v2.3 的基础上从头开始建立的。加密库 SEAL v2.3.0-4，它是基于 BFV 方案 [22]。我们给出了详细的端到端和在线运行时间的报告，以及通信费用。在线运行时间以及通信开销的详细报告。我们的协议在图 4 中详细报告了单线程和多线程情况下的端到端和在线运行时间。我们将接收器限制为最多 4 个线程，以模拟一个低功耗的 设备，而发送方最多使用 32 个线程，如表中所示。表中所示。图 5 显示了与非平衡 PSI 协议进行了比较 [5, 12, 47]。

我们在一个 32 核英特尔至强 CPU 上对协议进行了基准测试，该 CPU 有 256 GB 的内存。我们注意到，这台机器类似于 [12] 所使用的机器。12] 所使用的机器，而且他们的协议所报告的数字是直接从他们的论文中获得的。从他们的论文中直接获得。所有协议都是在局域网内运行的 所有协议都在局域网中运行，吞吐量为 10Gbps，延迟时间为亚毫秒。

image-20220524165807014

图 4：我们的协议在局域网设置中对不同的集合大小的性能指标。"发送方离线" 报告了初始化发送方集合所需的运行时间（秒）。这是非交互式的，可以与多个接收者重复使用。"在线" 报告了执行交集所需的端到端运行时间（秒），其中 "通信" 列报告了定向通信要求（MB）。 是发送方使用的线程数。接收者使用最大 个线程。

image-20220524170938877

图 5：我们的 PSI 协议与 [5, 12, 47] 在局域网环境下的不同集合大小的比较。所有的执行都是单线程的，除了 是 的执行，发送方有 32 个线程，接收方有 4 个线程。通信 / 存储的单位是 MB，运行时间是秒。发送方离线 " 列是发送方初始化其数据库所需的运行时间。它可以被重复使用，并且是非交互式的。

8.1 对称密钥 BFV 的改进通信

我们通过对 SEAL 进行一些修改，使用 BFV 方案的对称密钥变体而不是更常见的公钥变体，来进一步提高我们的通信成本。这样做的好处是，新加密的 BFV 密文（见 [22]）中的第二个多项式不必依赖于公钥，因此可以从一个随机种子中生成。因此，每个新加密的密码文的大小几乎减半，大大减少了我们的 通信。一旦发送方收到半大小的密码文，它可以扩展种子以获得完整的密码文。不幸的是，在同态乘法之后，确实没有办法回到半大小的表示，所以这种技术不能改善 通信。我们还可以利用协议中的各种权衡，将更多的通信放在 步骤中，然后将其减半，从而使总通信量显著提高（20 - 40%），计算开销可忽略不计。

8.2 不平衡的 PSI

图 4 包含了我们主要的一组性能数字，并展示了集合大小的广泛灵活性。对于发送方，我们考虑了 、 和 的集合大小，而接收方的集合大小在 和 之间。我们注意到，对于每个接收方的集合大小，可以增加大约 1.33 倍的项目，而由于布谷鸟表中的额外空间，性能上没有任何差别。然而，为了与其他没有参数限制的协议进行公平的比较，我们将四舍五入到最接近的 2 次方。

我们从最小的集合大小 和 的性能数字开始。对于这样一个小的交集，我们的协议是非常有效的，在一个单线程上需要不到一秒钟的在线时间，并且只有 3.9MB 的通信。当接收器集增加到 个项目时，我们观察到运行时间和通信量只增加了很少。到了我们最大的接收器集大小 ，我们观察到在线运行时间大约增加了 4.7 倍，通信量增加了 3 倍。这种与接收者集合大小有关的开销的亚线性增长归因于使用更有效的 FHE 参数的能力。关于发送方的离线运行时间，我们观察到在几乎所有的情况下，如果 ，单线程运行时间大约为 40 秒。唯一的例外是 的情况，其运行时间是原来的两倍。这是由于所使用的 FHE 参数允许有效的在线时间，但代价是离线阶段的计算量增加。

将发送方的集合大小增加到 时，我们观察到一个类似的趋势，即接收方最小的集合大小都能获得相同的性能。事实上，对于 ，利用相同的 FHE 参数，产生的单线程在线运行时间为 9.1 秒，通讯量为 8.2MB。选择对较小的集合大小使用超大的参数，是因为可以优化的参数之间存在高度复杂的相互作用，同时还可以保持 比特的计算安全水平。我们参考第 3.1 节，以获得更详细的解释。对于接收方的 个集合大小，我们观察到在单线程设置下，在线运行时间为 22 秒，通信量为 15.9MB。发送方的离线时间在单线程上需要 806 秒，或在 32 个线程上需要 32 秒。有趣的是，这个离线运行时间随着发送者的集合大小的增加而加快。除其他外，这是由于随着 增加，发送方的数据库中每个桶的项目更少，这反过来又减少了发送方在预处理中需要计算的多项式的程度，从而提高了性能。

此外，我们还考虑了 的情况，据我们所知，这是在两方设置中考虑过的最大的 PSI 集大小，只有在一个较弱的模型中才会被超越，即一个不受信任的第三方协助计算 [32]。在这种情况下，我们考虑接收器的集合大小为 ，并观察到当发送方和接收方分别使用 32 和 4 个线程时，在线阶段可以在短短 12 秒内完成。同时，在线阶段仅利用了 18.4MB 的通信。如此大的集合规模的主要影响是对发送方的离线运行时间。然而，在使用如此大的集合的情况下，该集合极有可能由一个强大的服务器持有，并且是相对静态的，在这种情况下，发送方可以在几次协议执行中摊销预处理的成本。我们还注意到，我们的协议允许在必要时只更新小的目标位置，从而快速添加和删除预处理的集合。此外，目前离线阶段的实现远非最佳，因为存在更有效的算法来计算发送方多项式的系数，这是主要瓶颈。

8.3 比较

我们现在开始与 [5, 47] 的基于 OPRF 的协议和 [12] 的基于 FHE 的协议进行比较。首先我们回顾一下 [5, 31, 47] 的协议范式。这些协议利用与我们的协议相同的基于 Diffie-Hellman 的 OPRF，其中发送方持有密钥 k 并将 OPRF 应用于其集合 以获得 。然后，接收方以交互方式计算出 。接下来，发送方将 发送给接收方，接收方从 中推断出交点 [31]。

这种方法的主要限制是，接收者需要在更大的集合 中进行线性通信。上述协议首先由 [31] 在恶意设置中描述，后来由 [5] 对半诚实设置进行优化。对于规模不大的 ，这种方法的效果相当好。例如，在 和接收者的 个项目集的情况下， 的通信量为 10MB。然而，进一步增加 到 或 ，开始变得不那么实用，分别有 160MB 和 2.6GB 的通信量。

这种模式最引人注目的特性之一是，在 的通信之后，接收者可以用 的通信和计算有效地检查 中 的成员身份。观察到这一点，[35, 47] 都建议在离线或预处理阶段发送 ，然后在线阶段在较小的集合中可以有线性开销，这提供了极好的性能。此外，可以进行许多与 的自适应集合交集，接收方每次都能使用不同的集合。这种方法的在线通信和运行时间在接收器的集合大小中保持线性。

在这个一般范式的基础上，[35, 47] 提出，可以使用布谷鸟过滤器或布隆过滤器等技术对编码集 进行压缩。[47] 表明，对于某些参数，布谷鸟过滤器可以减少大约 3 倍的通信量，使 和 的通信量分别下降到 48 和 806 MB。这种方法的缺点是，如此大的压缩量引入了相对较高的假阳性率，即 。也就是说，如果接收方有 个交叉点以外的项目，接收方输出错误项目的概率为 ，这对加密协议来说是非常高的。相比之下，我们的协议和 [12] 都提供了至少 的误判率，而且这个比率与接收者的集合大小无关。

此外，[47] 的通信复杂度在更大的集合规模中保持线性。在 的例子中，804 MB 的通信对许多应用来说可能是难以承受的。此外，为了使这种在线 - 离线技术发挥作用，接收器必须长期存储压缩的集合，这在移动设备上可能是不可接受的。与这种模式相反，我们基于 FHE 的协议实现了通信复杂度在更大的集合尺寸中是亚线性的，并且不需要接收者进行离线存储。当考虑到 和 时，总通信量小于 19MB，而 806MB：通信量提高了 43 倍，假阳性率提高了 226 倍。为了达到同等的假阳性率，例如在 [5] 协议中，通信量增加到 2.6GB-- 差距为 100 倍。

最后，在更新 时透露的信息方面，实现的安全性也有差异。在 [5, 35, 47] 的情况下，接收者确切地知道我们从 X 中插入和删除了多少个项目。更糟糕的是，从 中删除一个项目不能被强制执行，因为接收者可以简单地保留他们在 中持有的相应 OPRF 值。因此，即使在半诚实的模型中，删除也不能被强制执行。相比之下，我们的协议可以很容易地增加和删除项目，而不会向接收者泄露额外的信息。特别是，从 中删除一个项目的问题不会出现，因为只有发送者持有 。

与 [12] 相比，我们在许多方面都更有优势。首先回顾一下，[12] 实际上只限于 位的项目，而我们可以支持任意长度的项目。特别是，在 [12] 中，在 FHE 中被比较的实际项目只有 位，但使用相位 [43] 扩展到 位。我们的协议与此相反，在 FHE 计算中比较 位的项目。结合 [45] 的 "散列到更小的域" 技术，这足以支持我们的 PSI 集大小，同时实现 比特的统计安全性。

鉴于这一重大改进，我们的协议仍然实现了类似的通信开销，而且在线运行时间往往更好。例如，当比较 和 时，我们的协议在单线程的在线阶段需要 16MB 的通信和 22 秒，而 [12] 需要 20MB 和 40 秒。这在运行时间上几乎提高了 2 倍，在通信上提高了 27%，并且有能力比较任意长度的字符串。此外，当接收方有一个更小的集合时，我们的协议能够将 FHE 参数的规模更小，这使得通信量减少。例如，当接收方有 个或 个项目时，我们的协议分别需要 9.1 秒和 17.7 秒，并且只需要 8.2MB 的通信。另一方面，由于 [12] 进行的噪声淹没，他们无法利用更有效的 FHE 参数，同时也无法保持 比特的计算安全性。因此，我们的协议可以比 [12] 快 2 到 4 倍，而发送的数据量几乎是 [12] 的一半，同时支持任意长度的项目。

8.4 标签化 PSI

我们将我们的标签化 PSI 技术的性能与匿名通信协议 Pung [2, 3] 所使用的关键词 PIR 进行比较。Pung 协议允许一组客户通过一个服务器私下发送和检索信息，而服务器不了解关于对话的任何信息（包括元数据）。在该协议的每个纪元中，一个客户希望使用他们共享的一些秘密关键词从服务器上私下检索几个消息。这是用一个基于加法同态加密的单服务器 PIR 实现的。为了让客户获得发送给她的消息的索引，服务器向每个客户发送一个包含关键词到索引映射的布隆过滤器。Pung 还利用散列技术对多查询进行了优化。在一个设置中，客户端在每个纪元中检索 条消息。每条消息有 个字节，在服务器上共存储有 100 万条消息。我们使用标签化的 PSI 来实现检索过程，并在图 6 中把我们的性能与 [2] 进行了比较。从结果来看，我们发现标签化的 PSI 可以实现服务器在线计算时间减少 4.4 倍，通信量减少 6.8 倍。

image-20220524171006099
图 6：应用于 Pung 匿名通信协议的标签化的 PSI 的效果

参考文献

    1. Validating Leaked Passwords with k-Anonymity. https://blog.cloudflare. com/validating-leaked-passwords-with-k-anonymity/. (2018). Accessed: 201805-08.

  2. Sebastian Angel, Hao Chen, Kim Laine, and Srinath Setty. 2018. PIR with compressed queries and amortized query processing. In 2018 IEEE Symposium on Security and Privacy (SP). IEEE, 962–979.

  3. Sebastian Angel and Srinath Setty. 2016. Unobservable Communication over Fully Untrusted Infrastructure. In OSDI. 551–569.

  4. Jean-Claude Bajard, Julien Eynard, M Anwar Hasan, and Vincent Zucca. 2016. A full RNS variant of FV like somewhat homomorphic encryption schemes. In International Conference on Selected Areas in Cryptography. Springer, 423–442.

  5. Pierre Baldi, Roberta Baronio, Emiliano De Cristofaro, Paolo Gasti, and Gene Tsudik. 2011. Countering gattaca: efficient and secure testing of fully-sequenced human genomes. In Proceedings of the 18th ACM conference on Computer and communications security. ACM, 691–702.

  6. Dan Boneh, Craig Gentry, Shai Halevi, Frank Wang, and David J Wu. 2013. Private database queries using somewhat homomorphic encryption. In International Conference on Applied Cryptography and Network Security. Springer, 102–118.

  7. Zvika Brakerski. 2012. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. In CRYPTO (Lecture Notes in Computer Science), Reihaneh Safavi-Naini and Ran Canetti (Eds.), Vol. 7417. Springer, 868–886.

  8. Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. 2012. (Leveled) fully homomorphic encryption without bootstrapping. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. ACM, 309–325.

  9. Zvika Brakerski and Vinod Vaikuntanathan. 2011. Fully homomorphic encryption from ring-LWE and security for key dependent messages. In Advances in Cryptology–CRYPTO 2011. Springer, 505–524.

  10. Zvika Brakerski and Vinod Vaikuntanathan. 2014. Efficient fully homomorphic encryption from (standard) LWE. SIAM J. Comput. 43, 2 (2014), 831–871.

  11. Melissa Chase, Hao Chen, Jintai Ding, Shafi Goldwasser, Sergey Gorbunov, Jeffrey Hoffstein, Kristin Lauter, Satya Lokam, Dustin Moody, Travis Morrison, Amit Sahai, and Vinod Vaikuntanathan. 2017. Security of Homomorphic Encryption. Technical Report. HomomorphicEncryption.org, Redmond WA.

  12. Hao Chen, Kim Laine, and Peter Rindal. 2017. Fast private set intersection from homomorphic encryption. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. ACM, 1243–1255.

  13. Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. 2017. Homomorphic encryption for arithmetic of approximate numbers. In International Conference on the Theory and Application of Cryptology and Information Security. Springer, 409–437.

  14. Jung Hee Cheon, Miran Kim, and Myungsun Kim. 2015. Search-and-compute on encrypted data. In International Conference on Financial Cryptography and Data Security. Springer, 142–159.

  15. Jung Hee Cheon, Miran Kim, and Myungsun Kim. 2016. Optimized search-andcompute circuits and their application to query evaluation on encrypted data. IEEE Transactions on Information Forensics and Security 11, 1 (2016), 188–199.

  16. Jung Hee Cheon, Miran Kim, and Kristin Lauter. 2015. Homomorphic computation of edit distance. In International Conference on Financial Cryptography and Data Security. Springer, 194–212.

  17. Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachene. 2016. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. In International Conference on the Theory and Application of Cryptology and Information Security. Springer, 3–33.

  18. Benny Chor, Niv Gilboa, and Moni Naor. 1997. Private information retrieval by keywords. Citeseer.

  19. Michele Ciampi and Claudio Orlandi. 2018. Combining Private Set-Intersection with Secure Two-Party Computation. Technical Report. Cryptology ePrint Archive, Report 2018/105.

  20. Emiliano De Cristofaro, Paolo Gasti, and Gene Tsudik. 2012. Fast and private computation of cardinality of set intersection and union. In International Conference on Cryptology and Network Security. Springer, 218–231.

  21. Nathan Dowlin, Ran Gilad-Bachrach, Kim Laine, Kristin Lauter, Michael Naehrig, and John Wernsing. 2017. Manual for using homomorphic encryption for bioinformatics. Proc. IEEE 105, 3 (2017), 552–567.

  22. Junfeng Fan and Frederik Vercauteren. 2012. Somewhat Practical Fully Homomorphic Encryption. Cryptology ePrint Archive, Report 2012/144. (2012). http://eprint.iacr.org/.

  23. Michael J Freedman, Yuval Ishai, Benny Pinkas, and Omer Reingold. 2005. Keyword search and oblivious pseudorandom functions. In Theory of Cryptography Conference. Springer, 303–324.

  24. Craig Gentry. 2009. Fully homomorphic encryption using ideal lattices.. In STOC, Vol. 9. 169–178.

  25. Craig Gentry, Shai Halevi, and Nigel P Smart. 2012. Homomorphic evaluation of the AES circuit. In Advances in cryptology–crypto 2012. Springer, 850–867.

  26. Craig Gentry, Amit Sahai, and Brent Waters. 2013. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In CRYPTO (1) (Lecture Notes in Computer Science), Ran Canetti and Juan A. Garay (Eds.), Vol. 8042. Springer, 75–92. https://doi.org/10.1007/ 978- 3- 642- 40041- 4

  27. Shai Halevi and Victor Shoup. 2014. Algorithms in helib. In International cryptology conference. Springer, 554–571.

  28. W. Hart, F. Johansson, and S. Pancratz. 2013. FLINT: Fast Library for Number Theory. (2013). Version 2.4.0, http://flintlib.org.

  29. Carmit Hazay and Yehuda Lindell. 2008. Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries. In Theory of Cryptography, Ran Canetti (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 155–175.

  30. Mihaela Ion, Ben Kreuter, Erhan Nergiz, Sarvar Patel, Shobhit Saxena, Karn Seth, David Shanahan, and Moti Yung. 2017. Private Intersection-Sum Protocol with Applications to Attributing Aggregate Ad Conversions. Technical Report. Cryptology ePrint Archive, Report 2017/738.

  31. Stanisław Jarecki and Xiaomin Liu. 2010. Fast secure computation of set intersection. In International Conference on Security and Cryptography for Networks. Springer, 418–435.

  32. Seny Kamara, Payman Mohassel, Mariana Raykova, and Saeed Sadeghian. 2014. Scaling Private Set Intersection to Billion-Element Sets. In Financial Cryptography and Data Security, Nicolas Christin and Reihaneh Safavi-Naini (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 195–215.

  33. Alhassan Khedr, Glenn Gulak, and Vinod Vaikuntanathan. 2016. SHIELD: scalable homomorphic implementation of encrypted data-classifiers. IEEE Trans. Comput. 65, 9 (2016), 2848–2858.

  34. Andrey Kim, Yongsoo Song, Miran Kim, Keewoo Lee, and Jung Hee Cheon. 2018. Logistic Regression Model Training based on the Approximate Homomorphic Encryption. Cryptology ePrint Archive, Report 2018/254. (2018). https://eprint. iacr.org/2018/254.

  35. Ágnes Kiss, Jian Liu, Thomas Schneider, N Asokan, and Benny Pinkas. 2017. Private set intersection for unequal set sizes with mobile applications. Proceedings on Privacy Enhancing Technologies 2017, 4 (2017), 177–197.

  36. Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, and Ni Trieu. 2016. Efficient batched oblivious PRF with applications to private set intersection. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. ACM, 818–829.

  37. Moxie Marlinspike. 2014. The Difficulty Of Private Contact Discovery. A company sponsored blog post. (2014). https://whispersystems.org/blog/contact-discovery/.

  38. C. Meadows. 1986. A More Efficient Cryptographic Matchmaking Protocol for Use in the Absence of a Continuously Available Third Party. In 1986 IEEE Symposium on Security and Privacy. 134–134. https://doi.org/10.1109/SP.1986.10022

  39. Marcin Nagy, Emiliano De Cristofaro, Alexandra Dmitrienko, N Asokan, and Ahmad-Reza Sadeghi. 2013. Do I know you?: efficient and privacy-preserving common friend-finder protocols and applications. In Proceedings of the 29th Annual Computer Security Applications Conference. ACM, 159–168.

  40. Andrew Odlyzko. 2003. Privacy, economics, and price discrimination on the Internet. In Proceedings of the 5th international conference on Electronic commerce. ACM, 355–366.

  41. Femi Olumofin and Ian Goldberg. 2010. Privacy-preserving queries over relational databases. In International Symposium on Privacy Enhancing Technologies Symposium. Springer, 75–92.

  42. Michele Orrù, Emmanuela Orsini, and Peter Scholl. 2017. Actively secure 1-out-ofn OT extension with application to private set intersection. In CryptographersâĂŹ Track at the RSA Conference. Springer, 381–396.

  43. Benny Pinkas, Thomas Schneider, Gil Segev, and Michael Zohner. 2015. Phasing: Private set intersection using permutation-based hashing. In 24th USENIX Security Symposium (USENIX Security 15). 515–530.

  44. Benny Pinkas, Thomas Schneider, Christian Weinert, and Udi Wieder. 2018. Efficient circuit-based PSI via cuckoo hashing. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 125–157.

  45. Benny Pinkas, Thomas Schneider, and Michael Zohner. 2014. Faster Private Set Intersection Based on OT Extension.. In USENIX Security Symposium, Vol. 14. 797–812.

  46. Benny Pinkas, Thomas Schneider, and Michael Zohner. 2018. Scalable private set intersection based on OT extension. ACM Transactions on Privacy and Security (TOPS) 21, 2 (2018), 7.

  47. Amanda C Davi Resende and Diego F Aranha. 2018. Faster Unbalanced Private Set Intersection. Journal of Internet Services and Applications 9, 1 (2018), 1–18.

  48. Peter Rindal and Mike Rosulek. 2017. Malicious-Secure Private Set Intersection via Dual Execution. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS ’17). ACM, New York, NY, USA, 1229–1242. https://doi.org/10.1145/3133956.3134044

  49. Ronald L Rivest, Len Adleman, and Michael L Dertouzos. 1978. On data banks and privacy homomorphisms. Foundations of secure computation 4, 11 (1978), 169–180.

  50. Nigel P Smart and Frederik Vercauteren. 2014. Fully homomorphic SIMD operations. Designs, codes and cryptography 71, 1 (2014), 57–81.

  51. Frank Wang, Catherine Yun, Shafi Goldwasser, Vinod Vaikuntanathan, and Matei Zaharia. 2017. Splinter: Practical Private Queries on Public Data.. In NSDI. 299313.

附录 A 泄露的 PSI 的安全证明

定理 4：在随机预言机混合体中，在存在 OMGDH 硬组 以及语义安全的 - 有限级全同态加密方案 的情况下，图 8 的协议 以（非黑箱）模拟安全性安全地计算泄漏的 PSI 功能（图 7），其中 和 。

证明：证明该协议对恶意接收者是安全的，是定理 1 的一个直接延伸。

在恶意发送者的情况下，我们必须描述一个非黑盒模拟器，它可以提取发送者集合和泄漏函数，这些函数被转发到图 7 的理想功能。模拟器使用一个假的集合扮演接收者的角色，并在协议结束时提取发送者集合和函数，如下所示。

首先，模拟器从零知识证明中提取 OPRF 密钥 ，并使用随机预言机提取发送者用密钥 查询过的所有 OPRF 输入，并将其定义为它们的集合 。根据定义 3， 中所有项目的标签都是均匀分布的，并且发送者不能以不可忽略的概率构建一个解密为这些标签之一的密文。如果这一点不成立，那么这个发送者就可以用来构建一个矛盾的。也就是说，由于 中的输入的所有 OPRF 输出在 中均匀分布，我们可以将 OPRF 或随机预言机在输入 上的输出编程为定义 3 中的 ，将发送者的代码编程为 。如果发送者（ ）能够生成 的密文，那么这个密文就是一个矛盾，因为 FHE 方案被假定为 。

然后，泄漏函数定义如下。在输入 上，该函数将 OPRF 应用于 ，并对结果进行布谷鸟散列。通过检查发送者的代码，可以确定是否为给定的布谷鸟位置计算出了正确的标签。如果是这样，那么这个位置所代表的输入就由泄漏函数输出。然后，模拟器可以将发送者的集合和这个泄漏函数发送到理想功能（图 7）。

备注：在图 8 中加入了一个零知识证明，即发送者对所有 OPRF 的调用都使用相同的密钥。这主要是为了简化证明的论述。该证明必须处理发送方使用多个 OPRF 密钥的情况以及密钥未知的情况，例如发回一个随机值而不是 ，以取代零知识证明。这些情况可以通过在泄漏函数中加入加法逻辑来处理。

image-20220524171907540
图 7：理想的泄漏 PSI 功能
image-20220524171918924
图 8：带有泄漏的完整恶意 PSI 协议